
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>


// 翻转字符串里的单词
namespace S1 {
    class Solution {
    public:
        std::string reverseWords(std::string s) {
            int start = 0, end = 0;
            int n = s.length();

            std::vector<std::string> strs;
            while (start < n) {
                while (start < n && s[start] == ' '){
                    start ++;
                }

                if (start >= n) {
                    break;
                }
                end = start;
                while (end < n && s[end] != ' '){
                    end ++;
                }
                strs.push_back(s.substr(start, end - start));
                start = end;
            }
            std::string result; 
            for (auto it = strs.rbegin(); it != strs.rend(); ++it) {
                if (result.empty()) {
                    result += *it;
                } else {
                    result += " " + *it;
                }
            }

            return result;
        }
    };
}

namespace S2 {
    class Solution {
    public:
        std::string reverseWords(std::string s) {
            //1. 使用快慢指针 去掉头或者尾的空格 ，或者中间有两个空格
            int slow = 0;
            for (int fast = 0; fast < s.size(); ++fast) {
                if (s[fast] != ' ') {
                    if (slow != 0) {
                        s[slow++] = ' ';   // 如果不开头，添加一个空格 
                    }
                }
                // 复制当前单词的所有字符
                while(fast < s.size() && s[fast] != ' ') {
                    s[slow++] = s[fast++];
                }
            }
            s.resize(slow); // 截断字符串，去除尾部冗余

            std::reverse(s.begin(), s.end());

            // 这里也使用了双指针
            int start = 0;
            for (int end = 0; end <= s.size(); ++end) {
                // 遇到空格或字符串末尾，反转[start, end-1]的单词
                if (end == s.size() || s[end] == ' ') {
                    std::reverse(s.begin() + start, s.begin() + end);
                    start = end + 1; // 更新下一个单词的起始位置
                }
            }
            return s;
        }
    };
}

int main() {
    S2::Solution s;
    auto res = s.reverseWords("the sky is blue");

    std::cout << res << std::endl;
    return 0;
}